package leetcode.editor.cn;
//Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。 
//
// 游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。 
//
// Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此
//时手中 石子最多 的玩家 获胜 。 
//
// 假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入：piles = [5,3,4,5]
//输出：true
//解释：
//Alice 先开始，只能拿前 5 颗或后 5 颗石子 。
//假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
//如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。
//如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。
//这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。
// 
//
// 示例 2： 
//
// 
//输入：piles = [3,7,2,3]
//输出：true
// 
//
// 
//
// 提示： 
//
// 
// 2 <= piles.length <= 500 
// piles.length 是 偶数 
// 1 <= piles[i] <= 500 
// sum(piles[i]) 是 奇数 
// 
//
// Related Topics 数组 数学 动态规划 博弈 👍 490 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution154 {


    /**
     *
     *     因为题目有两个条件很重要：一是石头总共有偶数堆，石头的总数是奇数。
     *     这两个看似增加游戏公平性的条件，反而使该游戏成为了一个割韭菜游戏。
     *     我们以 piles=[2, 1, 9, 5] 讲解，假设这四堆石头从左到右的索引分别是 1，2，3，4。
     *
     *     如果我们把这四堆石头按索引的奇偶分为两组，即第 1、3 堆和第 2、4 堆，那么这两组石头的数量一定不同，也就是说一堆多一堆少。
     *     因为石头的总数是奇数，不能被平分。
     *
     * 而作为第一个拿石头的人，你可以控制自己拿到所有偶数堆，或者所有的奇数堆。
     *
     * 你最开始可以选择第 1 堆或第 4 堆。如果你想要偶数堆，你就拿第 4 堆，这样留给对手的选择只有第 1、3 堆，
     * 他不管怎么拿，第 2 堆又会暴露出来，你就可以拿。同理，如果你想拿奇数堆，你就拿第 1 堆，
     * 留给对手的只有第 2、4 堆，他不管怎么拿，第 3 堆又给你暴露出来了。
     *
     * 也就是说，你可以在第一步就观察好，奇数堆的石头总数多，还是偶数堆的石头总数多，然后步步为营，就一切尽在掌控之中了。
     *
     * @param piles
     * @return
     */
    public boolean stoneGame(int[] piles) {
        return true;
    }








    public boolean stoneGame1(int[] piles) {
        int n = piles.length;
        // 初始化 dp 数组
        // dp[i][j].fir = x 表示，对于 piles[i...j] 这部分石头堆，先手能获得的最高分数为 x。
        //
        // dp[i][j].sec = y 表示，对于 piles[i...j] 这部分石头堆，后手能获得的最高分数为 y。
        //
        // 举例理解一下，假设 piles = [2, 8, 3, 5]，索引从 0 开始，那么：
        //
        // dp[0][1].fir = 8 意味着：面对石头堆 [2, 8]，先手最多能够获得 8 分；4
        // dp[1][3].sec = 5 意味着：面对石头堆 [8, 3, 5]，后手最多能够获得 5 分。
        //
        // 我们想求的答案是先手和后手最终分数之差，按照这个定义也就是 dp[0][n-1].fir - dp[0][n-1].sec，
        // 即面对整个 piles，先手的最优得分和后手的最优得分之差。
        Pair[][] dp = new Pair[n][n];
        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++)
                dp[i][j] = new Pair(0, 0);

        // 填入 base case
        for (int i = 0; i < n; i++) {
            dp[i][i].fir = piles[i];
            dp[i][i].sec = 0;
        }


        /**
         * dp[i][j].fir = max(piles[i] + dp[i+1][j].sec, piles[j] + dp[i][j-1].sec)
         * dp[i][j].fir = max(     选择最左边的石头堆     ,     选择最右边的石头堆      )
         * # 解释：我作为先手，面对 piles[i...j] 时，有两种选择：
         * # 要么我选择最左边的那一堆石头，然后面对 piles[i+1...j]
         * # 但是此时轮到对方，相当于我变成了后手；
         * # 要么我选择最右边的那一堆石头，然后面对 piles[i...j-1]
         * # 但是此时轮到对方，相当于我变成了后手。
         *
         * if 先手选择左边:
         *     dp[i][j].sec = dp[i+1][j].fir
         * if 先手选择右边:
         *     dp[i][j].sec = dp[i][j-1].fir
         * # 解释：我作为后手，要等先手先选择，有两种情况：
         * # 如果先手选择了最左边那堆，给我剩下了 piles[i+1...j]
         * # 此时轮到我，我变成了先手；
         * # 如果先手选择了最右边那堆，给我剩下了 piles[i...j-1]
         * # 此时轮到我，我变成了先手。
         */
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                int left = piles[i] + dp[i + 1][j].sec;
                int right = piles[j] + dp[i][j - 1].sec;
                // 套用状态转移方程
                // 先手肯定会选择更大的结果，后手的选择随之改变
                if (left > right) {
                    dp[i][j].fir = left;
                    dp[i][j].sec = dp[i + 1][j].fir;
                } else {
                    dp[i][j].fir = right;
                    dp[i][j].sec = dp[i][j - 1].fir;
                }
            }
        }
        Pair res = dp[0][n - 1];
        return res.fir - res.sec >= 0;
    }


    class Pair {
        int fir, sec;

        Pair(int fir, int sec) {
            this.fir = fir;
            this.sec = sec;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
